
"""
116. 填充每个节点的下一个右侧节点指针
"""
from typing import Optional

from com.siyuan.part11.Node import Node


class Solution:

    """
    思路：将相邻的两个节点作为一个子节点，构造成一个三叉树，遍历这个三叉树，在前序的位置将两个节点连接
    """
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if not root:
            return None
        self.traverse(root.left, root.right)
        return root

    '''遍历三叉树'''
    def traverse(self, node1: 'Optional[Node]', node2: 'Optional[Node]'):
        if not node1 or not node2:
            return None

        # 前序位置链接
        node1.next = node2
        self.traverse(node1.left, node1.right)
        self.traverse(node1.right, node2.left)
        self.traverse(node2.left, node2.right)
